๐Ÿ‘ฉโ€๐Ÿ’ป 17471. ๊ฒŒ๋ฆฌ๋งจ๋”๋ง

@Seongukbaek Posted March 03, 2022 ยท Updated March 03, 2022 ยท 8 min read

๋ฌธ์ œ

๋ฐฑ์ค€์‹œ์˜ ์‹œ์žฅ ์ตœ๋ฐฑ์ค€์€ ์ง€๋‚œ ๋ช‡ ๋…„๊ฐ„ ๊ฒŒ๋ฆฌ๋งจ๋”๋ง์„ ํ†ตํ•ด์„œ ์ž์‹ ์˜ ๋‹น์—๊ฒŒ ์œ ๋ฆฌํ•˜๊ฒŒ ์„ ๊ฑฐ๊ตฌ๋ฅผ ํš์ •ํ–ˆ๋‹ค. ๊ฒฌ์ œํ•  ๊ถŒ๋ ฅ์ด ์—†์–ด์ง„ ์ตœ๋ฐฑ์ค€์€ ๊ถŒ๋ ฅ์„ ๋งค์šฐ ๋ถ€๋‹นํ•˜๊ฒŒ ํ–‰์‚ฌํ–ˆ๊ณ , ์‹ฌ์ง€์–ด๋Š” ์‹œ์˜ ์ด๋ฆ„๋„ ๋ฐฑ์ค€์‹œ๋กœ ๋ณ€๊ฒฝํ–ˆ๋‹ค. ์ด๋ฒˆ ์„ ๊ฑฐ์—์„œ๋Š” ์ตœ๋Œ€ํ•œ ๊ณตํ‰ํ•˜๊ฒŒ ์„ ๊ฑฐ๊ตฌ๋ฅผ ํš์ •ํ•˜๋ ค๊ณ  ํ•œ๋‹ค.

๋ฐฑ์ค€์‹œ๋Š” N๊ฐœ์˜ ๊ตฌ์—ญ์œผ๋กœ ๋‚˜๋ˆ„์–ด์ ธ ์žˆ๊ณ , ๊ตฌ์—ญ์€ 1๋ฒˆ๋ถ€ํ„ฐ N๋ฒˆ๊นŒ์ง€ ๋ฒˆํ˜ธ๊ฐ€ ๋งค๊ฒจ์ ธ ์žˆ๋‹ค. ๊ตฌ์—ญ์„ ๋‘ ๊ฐœ์˜ ์„ ๊ฑฐ๊ตฌ๋กœ ๋‚˜๋ˆ ์•ผ ํ•˜๊ณ , ๊ฐ ๊ตฌ์—ญ์€ ๋‘ ์„ ๊ฑฐ๊ตฌ ์ค‘ ํ•˜๋‚˜์— ํฌํ•จ๋˜์–ด์•ผ ํ•œ๋‹ค. ์„ ๊ฑฐ๊ตฌ๋Š” ๊ตฌ์—ญ์„ ์ ์–ด๋„ ํ•˜๋‚˜ ํฌํ•จํ•ด์•ผ ํ•˜๊ณ , ํ•œ ์„ ๊ฑฐ๊ตฌ์— ํฌํ•จ๋˜์–ด ์žˆ๋Š” ๊ตฌ์—ญ์€ ๋ชจ๋‘ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ์–ด์•ผ ํ•œ๋‹ค. ๊ตฌ์—ญ A์—์„œ ์ธ์ ‘ํ•œ ๊ตฌ์—ญ์„ ํ†ตํ•ด์„œ ๊ตฌ์—ญ B๋กœ ๊ฐˆ ์ˆ˜ ์žˆ์„ ๋•Œ, ๋‘ ๊ตฌ์—ญ์€ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ๋‹ค๊ณ  ํ•œ๋‹ค. ์ค‘๊ฐ„์— ํ†ตํ•˜๋Š” ์ธ์ ‘ํ•œ ๊ตฌ์—ญ์€ 0๊ฐœ ์ด์ƒ์ด์–ด์•ผ ํ•˜๊ณ , ๋ชจ๋‘ ๊ฐ™์€ ์„ ๊ฑฐ๊ตฌ์— ํฌํ•จ๋œ ๊ตฌ์—ญ์ด์–ด์•ผ ํ•œ๋‹ค.

์•„๋ž˜ ๊ทธ๋ฆผ์€ 6๊ฐœ์˜ ๊ตฌ์—ญ์ด ์žˆ๋Š” ๊ฒƒ์ด๊ณ , ์ธ์ ‘ํ•œ ๊ตฌ์—ญ์€ ์„ ์œผ๋กœ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ๋‹ค.

์•„๋ž˜๋Š” ๋ฐฑ์ค€์‹œ๋ฅผ ๋‘ ์„ ๊ฑฐ๊ตฌ๋กœ ๋‚˜๋ˆˆ 4๊ฐ€์ง€ ๋ฐฉ๋ฒ•์ด๋ฉฐ, ๊ฐ€๋Šฅํ•œ ๋ฐฉ๋ฒ•๊ณผ ๋ถˆ๊ฐ€๋Šฅํ•œ ๋ฐฉ๋ฒ•์— ๋Œ€ํ•œ ์˜ˆ์‹œ์ด๋‹ค.

๊ฐ€๋Šฅํ•œ ๋ฐฉ๋ฒ•: [1, 3, 4]์™€ [2, 5, 6]์œผ๋กœ ๋‚˜๋ˆ„์–ด์ ธ ์žˆ๋‹ค.

๊ฐ€๋Šฅํ•œ ๋ฐฉ๋ฒ•: [1, 2, 3, 4, 6]๊ณผ [5]๋กœ ๋‚˜๋ˆ„์–ด์ ธ ์žˆ๋‹ค.

๋ถˆ๊ฐ€๋Šฅํ•œ ๋ฐฉ๋ฒ•: [1, 2, 3, 4]์™€ [5, 6]์œผ๋กœ ๋‚˜๋ˆ„์–ด์ ธ ์žˆ๋Š”๋ฐ, 5์™€ 6์ด ์—ฐ๊ฒฐ๋˜์–ด ์žˆ์ง€ ์•Š๋‹ค.

๋ถˆ๊ฐ€๋Šฅํ•œ ๋ฐฉ๋ฒ•: ๊ฐ ์„ ๊ฑฐ๊ตฌ๋Š” ์ ์–ด๋„ ํ•˜๋‚˜์˜ ๊ตฌ์—ญ์„ ํฌํ•จํ•ด์•ผ ํ•œ๋‹ค.

๊ณตํ‰ํ•˜๊ฒŒ ์„ ๊ฑฐ๊ตฌ๋ฅผ ๋‚˜๋ˆ„๊ธฐ ์œ„ํ•ด ๋‘ ์„ ๊ฑฐ๊ตฌ์— ํฌํ•จ๋œ ์ธ๊ตฌ์˜ ์ฐจ์ด๋ฅผ ์ตœ์†Œ๋กœ ํ•˜๋ ค๊ณ  ํ•œ๋‹ค. ๋ฐฑ์ค€์‹œ์˜ ์ •๋ณด๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, ์ธ๊ตฌ ์ฐจ์ด์˜ ์ตœ์†Ÿ๊ฐ’์„ ๊ตฌํ•ด๋ณด์ž.

์ž…๋ ฅ

  • ์ฒซ์งธ ์ค„์— ๊ตฌ์—ญ์˜ ๊ฐœ์ˆ˜ N์ด ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ ์ค„์— ๊ตฌ์—ญ์˜ ์ธ๊ตฌ๊ฐ€ 1๋ฒˆ ๊ตฌ์—ญ๋ถ€ํ„ฐ N๋ฒˆ ๊ตฌ์—ญ๊นŒ์ง€ ์ˆœ์„œ๋Œ€๋กœ ์ฃผ์–ด์ง„๋‹ค. ์ธ๊ตฌ๋Š” ๊ณต๋ฐฑ์œผ๋กœ ๊ตฌ๋ถ„๋˜์–ด์ ธ ์žˆ๋‹ค.
  • ์…‹์งธ ์ค„๋ถ€ํ„ฐ N๊ฐœ์˜ ์ค„์— ๊ฐ ๊ตฌ์—ญ๊ณผ ์ธ์ ‘ํ•œ ๊ตฌ์—ญ์˜ ์ •๋ณด๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๊ฐ ์ •๋ณด์˜ ์ฒซ ๋ฒˆ์งธ ์ •์ˆ˜๋Š” ๊ทธ ๊ตฌ์—ญ๊ณผ ์ธ์ ‘ํ•œ ๊ตฌ์—ญ์˜ ์ˆ˜์ด๊ณ , ์ดํ›„ ์ธ์ ‘ํ•œ ๊ตฌ์—ญ์˜ ๋ฒˆํ˜ธ๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๋ชจ๋“  ๊ฐ’์€ ์ •์ˆ˜๋กœ ๊ตฌ๋ถ„๋˜์–ด์ ธ ์žˆ๋‹ค.
  • ๊ตฌ์—ญ A๊ฐ€ ๊ตฌ์—ญ B์™€ ์ธ์ ‘ํ•˜๋ฉด ๊ตฌ์—ญ B๋„ ๊ตฌ์—ญ A์™€ ์ธ์ ‘ํ•˜๋‹ค. ์ธ์ ‘ํ•œ ๊ตฌ์—ญ์ด ์—†์„ ์ˆ˜๋„ ์žˆ๋‹ค.

์ถœ๋ ฅ

  • ์ฒซ์งธ ์ค„์— ๋ฐฑ์ค€์‹œ๋ฅผ ๋‘ ์„ ๊ฑฐ๊ตฌ๋กœ ๋‚˜๋ˆ„์—ˆ์„ ๋•Œ, ๋‘ ์„ ๊ฑฐ๊ตฌ์˜ ์ธ๊ตฌ ์ฐจ์ด์˜ ์ตœ์†Ÿ๊ฐ’์„ ์ถœ๋ ฅํ•œ๋‹ค. ๋‘ ์„ ๊ฑฐ๊ตฌ๋กœ ๋‚˜๋ˆŒ ์ˆ˜ ์—†๋Š” ๊ฒฝ์šฐ์—๋Š” -1์„ ์ถœ๋ ฅํ•œ๋‹ค.

๐Ÿ“ Logic

class Dosi { ArrayList<Integer>[] dosi; int[] population; int[] area; boolean[] visited; int size; int answer = Integer.MAX_VALUE; }
  • ์„ ๊ฑฐ๊ตฌ์˜ ์ •๋ณด๋ฅผ ๋‹ด๋‹นํ•˜๋Š” ํด๋ž˜์Šค์ด๋‹ค.
public int searchDivision();
  • ์„ ๊ฑฐ๊ตฌ ๋ถ„ํ•  ๋ฉ”์†Œ๋“œ๋ฅผ ํ˜ธ์ถœํ•˜๊ณ , ์ตœ์†Ÿ๊ฐ’์„ ๋น„๊ตํ•ด ์ตœ์ข…์ ์œผ๋กœ ์ถœ๋ ฅํ•ด์•ผ ํ•  ๊ฐ’์„ ๋ฐ˜ํ™˜ํ•˜๋Š” ํ•จ์ˆ˜์ด๋‹ค.
private void dfs(int n);
  • ์žฌ๊ท€์ ์œผ๋กœ ํ˜ธ์ถœ๋˜๋ฉด์„œ, ๋ชจ๋“  ์„ ๊ฑฐ๊ตฌ ๋ถ„ํ• ๋ฒ•์„ DFS๋ฐฉ์‹์œผ๋กœ ์™„์ „ ํƒ์ƒ‰ํ•˜๋ฉฐ ์„ ๊ฑฐ๊ตฌ๊ฐ€ 2๊ฐœ๋กœ ๋ถ„ํ•  ๊ฐ€๋Šฅํ•œ ๊ฒฝ์šฐ์—๋งŒ ์ธ๊ตฌ์ˆ˜ ์ฐจ์ด๋ฅผ ๊ณ„์† ์—…๋ฐ์ดํŠธํ•˜๋Š” ๋ฉ”์†Œ๋“œ์ด๋‹ค.
private void bfs(int idx, int areaN);
  • ์„ ๊ฑฐ๊ตฌ ๋ถ„ํ•  ํ›„, ๋ฐฉ๋ฌธ์—ฌ๋ถ€๋ฅผ ์—…๋ฐ์ดํŠธํ•˜๊ธฐ ์œ„ํ•ด BFS ๋ฐฉ์‹์œผ๋กœ ์ˆ˜ํ–‰๋˜๋Š” ๋ฉ”์†Œ๋“œ์ด๋‹ค.

๐Ÿ“„ CODE

์ฝ”๋“œ ๋ณด๊ธฐ/์ ‘๊ธฐ๐Ÿ’ซ
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; class Dosi { ArrayList<Integer>[] dosi; int[] population; int[] area; boolean[] visited; int size; int answer = Integer.MAX_VALUE; public Dosi(int N) { dosi = new ArrayList[N+1]; for (int i = 1; i <= N; i++) { dosi[i] = new ArrayList<>(); } area = new int[N + 1]; size = N; } public int searchDivision() { dfs(1); if (answer == Integer.MAX_VALUE) return -1; return answer; } private void dfs(int n) { if (n == size + 1) { int pop1=0, pop2=0; for (int i = 1; i <= size; i++) { if (area[i] == 1) pop1 += population[i-1]; else pop2 += population[i-1]; } visited = new boolean[size + 1]; int cnt = 0; for (int i = 1; i <= size; i++) { if (!visited[i]) { bfs(i, area[i]); cnt++; } } if (cnt == 2) answer = Math.min(answer, Math.abs(pop1 - pop2)); return; } area[n] = 1; dfs(n + 1); area[n] = 2; dfs(n + 1); } private void bfs(int idx, int areaN) { Queue<Integer> q = new LinkedList<>(); visited[idx] = true; q.add(idx); while (!q.isEmpty()) { int now = q.poll(); for(int i = 0; i < dosi[now].size(); i++) { int next = dosi[now].get(i); if(area[next] == areaN && !visited[next]) { q.add(next); visited[next] = true; } } } } } public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); String[] line; Dosi d = new Dosi(N); d.population = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray(); for (int i = 0; i < N; i++) { line = br.readLine().split(" "); for (int j = 0; j < Integer.parseInt(line[0]); j++) { d.dosi[i+1].add(Integer.parseInt(line[j+1])); } } System.out.println(d.searchDivision()); br.close(); } }

โœ๏ธ Review

  • ๋Œ€๋žต์ ์œผ๋กœ ๊ตฌ์ƒํ•œ ๋ฐฉ๋ฒ•์€,

    • ๋ถ„ํ• ์ด ๊ฐ€๋Šฅํ•œ ๋ฐฉ๋ฒ•์œผ๋กœ ์„ ๊ฑฐ๊ตฌ๋ฅผ ๋‘ ๊ฐœ๋กœ ๋ถ„ํ• 
    • ๋ถ„ํ• ํ•œ ๊ฒฝ์šฐ ์ค‘, ์ธ๊ตฌ ์ฐจ์ด๋ฅผ ๊ณ„์† ์—…๋ฐ์ดํŠธํ•˜๋Š” ๋ฐฉ์‹์œผ๋กœ ๊ฐ€์žฅ ์ตœ์†Œ๊ฐ€ ๋˜๋Š” ๋ถ„ํ• ๋ฒ•์„ ํƒ์ƒ‰
  • ๊ทธ๋Ÿฐ๋ฐ ์–ด๋–ป๊ฒŒ ์„ ๊ฑฐ๊ตฌ๋ฅผ ๋ถ„ํ• ํ•ด์•ผํ•˜๋Š”๊ฐ€๊ฐ€ ๊ณ ๋ฏผ์ด์—ˆ๋‹ค. ๊ทธ๋ž˜์„œ ๊ฒŒ์‹œํŒ์—์„œ "0๋ฒˆ ๊ตฌ์—ญ์ด ํฌํ•จ๋œ ์„ ๊ฑฐ๊ตฌ vs 0๋ฒˆ ๊ตฌ์—ญ์ด ํฌํ•จ๋˜์ง€ ์•Š์€ ์„ ๊ฑฐ๊ตฌ" ๋ผ๋Š” ์•„์ด๋””์–ด๋ฅผ ๋ฐœ๊ฒฌํ•ด ์ƒ๊ฐํ•ด๋ณด์•˜๋‹ค.

    • ์—ญ์‹œ๋‚˜ ๊ตฌํ˜„์—์„œ ๋ง‰ํ˜€ ์•„๋ž˜ ๋ธ”๋กœ๊ทธ๋ฅผ ์ฐธ๊ณ ํ–ˆ๋‹ค...
  • ๋งค๋ฒˆ ๋ฌธ์ œ๋ฅผ ์‹œ์ž‘ํ•  ๋•Œ ์–ด๋–ป๊ฒŒ ํ•˜๋ฉด ๊น”๋”ํ•˜๊ฒŒ ์ž…๋ ฅ์„ ๋ฐ›์•„ ์ €์žฅํ•  ์ˆ˜ ์žˆ์„๊นŒ๋ฅผ ๊ณ ๋ฏผํ•˜๋Š”๋ฐ, ์ด๋ฒˆ์—๋Š” ์ข€ ์ƒˆ๋กœ์šด ๋ฌธ๋ฒ•์„ ์‚ฌ์šฉํ•ด๋ณด์•˜๋‹ค.

    • String[] tokens ์— split(" ") ํ•œ ๊ฒฐ๊ณผ๋ฅผ ๋งค๋ฒˆ ๋‹ด์•˜๋‹ค๊ฐ€ ์ •์ˆ˜๋กœ ํŒŒ์‹ฑํ•˜์—ฌ ๋‹ค์‹œ ์ €์žฅํ–ˆ๋Š”๋ฐ, ์ด๋ฒˆ์—” ๋ฌธ์ž์—ด ํ•œ ์ค„์„ ๋ฐ›์•„ ๊ณต๋ฐฑ ๊ธฐ์ค€์œผ๋กœ ๋‚˜๋ˆ„๋ฉด์„œ ๋ฐ”๋กœ ์ •์ˆ˜ํ˜• ๋ฐฐ์—ด์— ์ €์žฅํ•˜๋Š” ๋ฐฉ์‹์„ ์‚ฌ์šฉํ•ด๋ณด์•˜๋‹ค.

๐Ÿ“• ์ถœ์ฒ˜

Baekjoon : https://www.acmicpc.net/problem/17471

์ฐธ๊ณ 

https://moonsbeen.tistory.com/254

@Seongukbaek
๋ฐฐ์šฐ๊ณ  ์ •๋ฆฌํ•˜๊ณ  ๊ณต์œ ํ•˜๋Š” ๋Œ€ํ•™์ƒ ๋ฐฑ์„ฑ์šฑ์ž…๋‹ˆ๋‹ค ๐Ÿ˜€